{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Compare Strings by Frequency of the Smallest Character"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSmallerByFrequency"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #比较字符串最小字母出现频次"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>定义一个函数 <code>f(s)</code>，统计 <code>s</code>  中<strong>（按字典序比较）最小字母的出现频次</strong> ，其中 <code>s</code> 是一个非空字符串。</p>\n",
    "\n",
    "<p>例如，若 <code>s = \"dcce\"</code>，那么 <code>f(s) = 2</code>，因为字典序最小字母是 <code>\"c\"</code>，它出现了 2 次。</p>\n",
    "\n",
    "<p>现在，给你两个字符串数组待查表 <code>queries</code> 和词汇表 <code>words</code> 。对于每次查询 <code>queries[i]</code> ，需统计 <code>words</code> 中满足 <code>f(queries[i])</code> < <code>f(W)</code> 的<strong> 词的数目</strong> ，<code>W</code> 表示词汇表 <code>words</code> 中的每个词。</p>\n",
    "\n",
    "<p>请你返回一个整数数组 <code>answer</code> 作为答案，其中每个 <code>answer[i]</code> 是第 <code>i</code> 次查询的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queries = [\"cbd\"], words = [\"zaaaz\"]\n",
    "<strong>输出：</strong>[1]\n",
    "<strong>解释：</strong>查询 f(\"cbd\") = 1，而 f(\"zaaaz\") = 3 所以 f(\"cbd\") < f(\"zaaaz\")。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>queries = [\"bbb\",\"cc\"], words = [\"a\",\"aa\",\"aaa\",\"aaaa\"]\n",
    "<strong>输出：</strong>[1,2]\n",
    "<strong>解释：</strong>第一个查询 f(\"bbb\") < f(\"aaaa\")，第二个查询 f(\"aaa\") 和 f(\"aaaa\") 都 > f(\"cc\")。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= queries.length <= 2000</code></li>\n",
    "\t<li><code>1 <= words.length <= 2000</code></li>\n",
    "\t<li><code>1 <= queries[i].length, words[i].length <= 10</code></li>\n",
    "\t<li><code>queries[i][j]</code>、<code>words[i][j]</code> 都由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [compare-strings-by-frequency-of-the-smallest-character](https://leetcode.cn/problems/compare-strings-by-frequency-of-the-smallest-character/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [compare-strings-by-frequency-of-the-smallest-character](https://leetcode.cn/problems/compare-strings-by-frequency-of-the-smallest-character/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"cbd\"]\\n[\"zaaaz\"]', '[\"bbb\",\"cc\"]\\n[\"a\",\"aa\",\"aaa\",\"aaaa\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def getF(w):\n",
    "            minC = ord(w[0])\n",
    "            cnt = 0\n",
    "            for c in w:\n",
    "                if ord(c) < minC:\n",
    "                    minC = ord(c)\n",
    "                    cnt = 1\n",
    "                elif ord(c) == minC:\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        freq = [0] * 12\n",
    "        for word in words:\n",
    "            freq[getF(word)] += 1\n",
    "\n",
    "        # print(freq)\n",
    "        \n",
    "        for i in range(9, 0, -1):\n",
    "            freq[i] += freq[i+1]\n",
    "\n",
    "        # print(freq)\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            # print(q)\n",
    "            # print(getF(q)+1)\n",
    "            ans.append(freq[getF(q)+1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def getF(w):\n",
    "            minC = ord(w[0])\n",
    "            cnt = 0\n",
    "            for c in w:\n",
    "                if ord(c) < minC:\n",
    "                    minC = ord(c)\n",
    "                    cnt = 1\n",
    "                elif ord(c) == minC:\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        freq = [0] * 12\n",
    "        for word in words:\n",
    "            freq[getF(word)] += 1\n",
    "        \n",
    "        for i in range(9, 0, -1):\n",
    "            freq[i] += freq[i+1]\n",
    "\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            ans.append(freq[getF(q)+1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries_frequency = []\n",
    "        words_frequency = []\n",
    "\n",
    "\n",
    "        for querie in queries:\n",
    "            querie = sorted(querie)\n",
    "            start = 0\n",
    "            for q in querie:\n",
    "                if q != querie[0]:\n",
    "                    break\n",
    "                start += 1\n",
    "            queries_frequency.append(start)\n",
    "\n",
    "\n",
    "        for word in words:\n",
    "            word = sorted(word)\n",
    "            start = 0\n",
    "            for q in word:\n",
    "                if q != word[0]:\n",
    "                    break\n",
    "                start += 1\n",
    "            words_frequency.append(start)\n",
    "        result = [sum([1 for w in words_frequency if w > q]) for q in queries_frequency]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        for i in range(len(queries)):\n",
    "            queries[i]=sorted(collections.Counter(queries[i]).items(),key=lambda x:x[0])\n",
    "        for i in range(len(words)):\n",
    "            words[i]=sorted(collections.Counter(words[i]).items(),key=lambda x:x[0])\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            temp=0\n",
    "            for w in words:\n",
    "                if w[0][1]>q[0][1]:\n",
    "                    temp+=1\n",
    "            ans.append(temp)\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        ch = 'z'\n",
    "        for c in s:\n",
    "            if c < ch:\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "            elif c == ch:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        count = [0] * 12\n",
    "        for s in words:\n",
    "            count[self.f(s)] += 1\n",
    "        for i in range(9, 0, -1):\n",
    "            count[i] += count[i + 1]\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            res.append(count[self.f(s) + 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        ch = 'z'\n",
    "        for c in s:\n",
    "            if c < ch:\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "            elif c == ch:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        count = [0] * 12\n",
    "        for s in words:\n",
    "            count[self.f(s)] += 1\n",
    "        for i in range(9, 0, -1):\n",
    "            count[i] += count[i + 1]\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            res.append(count[self.f(s) + 1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        ch = 'z'\n",
    "        for c in s:\n",
    "            if c < ch:\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "            elif c == ch:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        count = sorted(self.f(w) for w in words)\n",
    "        n = len(words)\n",
    "        return [n - bisect_right(count, self.f(q)) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        for i in range(len(queries)):\n",
    "            queries[i]=sorted(collections.Counter(queries[i]).items(),key=lambda x:x[0])\n",
    "        for i in range(len(words)):\n",
    "            words[i]=sorted(collections.Counter(words[i]).items(),key=lambda x:x[0])\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            temp=0\n",
    "            for w in words:\n",
    "                if w[0][1]>q[0][1]:\n",
    "                    temp+=1\n",
    "            ans.append(temp)\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def getVal(aStr):\n",
    "            r = [0] * 26\n",
    "            b = ord('a')\n",
    "            ret = [26, 0]\n",
    "            for c in aStr:\n",
    "                i = ord(c) - b\n",
    "                r[i] += 1\n",
    "                if i <= ret[0]:\n",
    "                    ret[0] = i\n",
    "                    ret[1] = r[i]\n",
    "            return ret[1]\n",
    "        q = []\n",
    "        for w in words:\n",
    "            heapq.heappush(q, getVal(w))\n",
    "        ld = len(q)\n",
    "        dat = [heapq.heappop(q) for _ in range(ld)]\n",
    "        ret = []\n",
    "\n",
    "        for q in queries:\n",
    "            v = getVal(q)\n",
    "            #print(f\"v{v} q {q} dat {dat}\")\n",
    "            ret.append(ld - bisect.bisect_right(dat, v))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "def f(word:str) -> int:\n",
    "    count = 0\n",
    "    c = \"z\"\n",
    "    for w in word:\n",
    "        if w < c:\n",
    "            count = 1\n",
    "            c = w\n",
    "        elif w == c:\n",
    "            count += 1\n",
    "    return count\n",
    "\n",
    "def bisect(list,v) -> int:\n",
    "    len = list.__len__()\n",
    "    if len == 0:\n",
    "        return 0\n",
    "    if list[0] > v:\n",
    "        return len\n",
    "    if list[-1] <= v:\n",
    "        return 0\n",
    "    st = 0\n",
    "    ed = len\n",
    "    for i in range(0,len):\n",
    "        id = ( st + ed ) // 2\n",
    "        # print(st,id,ed)\n",
    "        if list[id] <= v and list[id + 1] > v:\n",
    "            return len - id - 1\n",
    "        elif list[id] > v:\n",
    "            ed = id\n",
    "        elif list[id + 1] <= v:\n",
    "            st = id + 1    \n",
    "    \n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        wf = list(map(f,words))\n",
    "        wf.sort()\n",
    "        # print(wf)\n",
    "        return list(map(lambda q: bisect(wf,q),map(f,queries)))      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries_frequency = []\n",
    "        words_frequency = []\n",
    "        for querie in queries:\n",
    "            queries_frequency.append(Counter(querie)[min(querie)])\n",
    "\n",
    "        for word in words:\n",
    "            words_frequency.append(Counter(word)[min(word)])\n",
    "        \n",
    "        result = []\n",
    "        for q in queries_frequency:\n",
    "            cnt = sum([1 for w in words_frequency if w > q])\n",
    "            result.append(cnt)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            for i in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                if i in s:\n",
    "                    return s.count(i)\n",
    "        \n",
    "        ans = []\n",
    "        for i, item in enumerate(words):\n",
    "            words[i] = f(item)\n",
    "        words.sort()\n",
    "        n = len(words)\n",
    "        for i in queries:\n",
    "            tmp = bisect_right(words, f(i))\n",
    "            if tmp == n or words[tmp] != f(i):\n",
    "                ans.append(n - bisect_right(words, f(i)))\n",
    "                continue\n",
    "            \n",
    "            ans.append(n - bisect_right(words, f(i)) - 1)\n",
    "            # print(words, f(i), bisect_right(words, f(i)))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def _f(s):\n",
    "            return sorted(Counter(s).items())[0][1]\n",
    "\n",
    "        words_freq = []\n",
    "        for w in words:\n",
    "            words_freq.append(_f(w))\n",
    "        words_freq.sort()\n",
    "\n",
    "        answers = []\n",
    "        for q in queries:\n",
    "            q_freq = _f(q)\n",
    "            idx = bisect.bisect(words_freq, q_freq)\n",
    "            answers.append(len(words_freq) - idx)\n",
    "        return answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            count = 0\n",
    "            char = 'z'\n",
    "\n",
    "            for letter in s:\n",
    "                if letter < char:\n",
    "                    char = letter\n",
    "                    count = 1\n",
    "                \n",
    "                elif letter == char:\n",
    "                    count += 1\n",
    "            \n",
    "            return count\n",
    "        \n",
    "        count_list = [0] * 12\n",
    "        for s in words:\n",
    "            # instead of using count_list[f(s)] = 1\n",
    "            # becasue words['a', 'a'] may occur same words\n",
    "            count_list[f(s)] += 1\n",
    "        \n",
    "        for i in range(9, 0 ,-1):\n",
    "            # ['a', 'aa']\n",
    "            # occur twice must occur three times as well\n",
    "            count_list[i] += count_list[i + 1]\n",
    "\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            res.append(count_list[f(s) + 1])\n",
    "        return res\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(w):\n",
    "            cnt = Counter(w)\n",
    "            return cnt[min(cnt.keys())]\n",
    "\n",
    "        for i in range(len(words)):\n",
    "            words[i] = f(words[i])\n",
    "        words.sort()\n",
    "        n = len(words)\n",
    "        \n",
    "        for i in range(len(queries)):\n",
    "            queries[i] = n - bisect_right(words, f(queries[i]))\n",
    "        return queries\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            for i in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                if i in s:\n",
    "                    return s.count(i)\n",
    "        \n",
    "        ans = []\n",
    "        for i, item in enumerate(words):\n",
    "            words[i] = f(item)\n",
    "        words.sort()\n",
    "        n = len(words)\n",
    "        for i in queries:\n",
    "            fi = f(i)\n",
    "            pos = bisect_right(words, fi)\n",
    "            if pos == n or words[pos] != fi:\n",
    "                ans.append(n - pos)\n",
    "                continue\n",
    "\n",
    "            ans.append(n - pos - 1)\n",
    "            # print(words, f(i), bisect_right(words, f(i)))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s:str) -> int:\n",
    "        cnt = 0\n",
    "        ch = 'z'\n",
    "        for c in s:\n",
    "            if c < ch:\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "            elif c == ch:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        count = [0] * 20\n",
    "        for s in words:\n",
    "            count[self.f(s)] += 1\n",
    "        \n",
    "        for i in range(9, 0, -1):\n",
    "            count[i] += count[i+1]\n",
    "        res = []\n",
    "        print(count)\n",
    "        for s in queries:\n",
    "            res.append(count[self.f(s)+1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            from collections import defaultdict\n",
    "            freq = defaultdict(int)\n",
    "\n",
    "            for i in s:\n",
    "                freq[i] = freq[i]+1\n",
    "\n",
    "            return freq[min(freq.keys())]\n",
    "\n",
    "        def func(queries,words):\n",
    "            result =[]\n",
    "\n",
    "            query_freq = [f(s) for s in queries]\n",
    "            word_freq = [f(s) for s in words]\n",
    "\n",
    "            for i in query_freq:\n",
    "                count =0 \n",
    "                for j in word_freq:\n",
    "                    if i<j:\n",
    "                        count+=1\n",
    "                result.append(count) \n",
    "\n",
    "            return result\n",
    "\n",
    "        return func(queries,words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        lst=[]\n",
    "        for i in queries:\n",
    "            que = sorted(i)\n",
    "            fq = i.count(que[0])\n",
    "            cont = 0\n",
    "            for j in words:\n",
    "                wo = sorted(j)\n",
    "                fw = j.count(wo[0])\n",
    "                if fq < fw:\n",
    "                    cont += 1\n",
    "            lst.append(cont)\n",
    "        return(lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        ch = 'z'\n",
    "        for c in s:\n",
    "            if c < ch:\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "            elif c == ch:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        count = [0] * 12\n",
    "        for s in words:\n",
    "            count[self.f(s)] += 1\n",
    "        for i in range(9, 0, -1):\n",
    "            count[i] += count[i + 1]\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            res.append(count[self.f(s) + 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        words_count=[]\n",
    "        for word in words:\n",
    "            words_count.append(self.countMinLetter(word))\n",
    "        words_count.sort()\n",
    "        words_num=len(words)\n",
    "        ans=[]\n",
    "        for q in queries:\n",
    "            q_count=self.countMinLetter(q)\n",
    "            ans.append(words_num-bisect.bisect_right(words_count,q_count))\n",
    "            \n",
    "        return ans\n",
    "            \n",
    "\n",
    "    def countMinLetter(self,s):\n",
    "        count=1\n",
    "        cur=s[0]\n",
    "        for i in range(1,len(s)):\n",
    "            if ord(cur)==ord(s[i]):\n",
    "                count+=1\n",
    "            elif ord(cur)>ord(s[i]):\n",
    "                cur=s[i]\n",
    "                count=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = self.StrToInt(queries)\n",
    "        words = self.StrToInt(words)\n",
    "\n",
    "        answer = []\n",
    "\n",
    "        for index, query in enumerate(queries):\n",
    "            sub_answer = 0\n",
    "            for word in words:\n",
    "                if query < word:\n",
    "                    sub_answer += 1\n",
    "\n",
    "            answer.append(sub_answer)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "    def StrToInt(self, data: List[str]) -> List[int]:\n",
    "        new_list = []\n",
    "\n",
    "        for i in data:\n",
    "            min_ord = 1000\n",
    "            min_count = 0\n",
    "\n",
    "            for ii in i:\n",
    "                if ord(ii) < min_ord:\n",
    "                    min_ord = ord(ii)\n",
    "                    min_count = 1\n",
    "                if ord(ii) == min_ord:\n",
    "                    min_count += 1\n",
    "\n",
    "            new_list.append(min_count)\n",
    "        \n",
    "        return new_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        count = [0] * 12\n",
    "        for s in words:\n",
    "            count[self.f(s)] += 1\n",
    "        for i in range(9, 0, -1):\n",
    "            count[i] += count[i + 1]\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            res.append(count[self.f(s) + 1])\n",
    "        return res\n",
    "\n",
    "    \n",
    "    def f(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        ch = min(s)\n",
    "        for c in s:\n",
    "            if c == ch:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "def f(word:str) -> int:\n",
    "    count = 0\n",
    "    c = \"z\"\n",
    "    for w in word:\n",
    "        if w < c:\n",
    "            count = 1\n",
    "            c = w\n",
    "        elif w == c:\n",
    "            count += 1\n",
    "    return count\n",
    "\n",
    "def bisect(list,v) -> int:\n",
    "    len = list.__len__()\n",
    "    if len == 0:\n",
    "        return 0\n",
    "    if list[0] > v:\n",
    "        return len\n",
    "    if list[-1] <= v:\n",
    "        return 0\n",
    "    st = 0\n",
    "    ed = len\n",
    "    for i in range(0,len):\n",
    "        id = ( st + ed ) // 2\n",
    "        # print(st,id,ed)\n",
    "        if list[id] <= v and list[id + 1] > v:\n",
    "            return len - id - 1\n",
    "        elif list[id] > v:\n",
    "            ed = id\n",
    "        elif list[id + 1] <= v:\n",
    "            st = id + 1    \n",
    "    \n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        wf = list(map(f,words))\n",
    "        wf.sort()\n",
    "        # print(wf)\n",
    "        return list(map(lambda q: bisect(wf,q),map(f,queries)))      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def countmin(s):\n",
    "            num = 500\n",
    "            count = 0\n",
    "            for i in s:\n",
    "                if ord(i) < num:\n",
    "                    count = 1\n",
    "                    num = ord(i)\n",
    "                elif ord(i) == num:\n",
    "                    count += 1\n",
    "            return count\n",
    "\n",
    "        querie_count = [countmin(s) for s in queries]\n",
    "        word_count = [countmin(s) for s in words]\n",
    "        res = [0] * len(queries)\n",
    "        for i in range(len(querie_count)):\n",
    "            for j in word_count:\n",
    "                if querie_count[i] < j:\n",
    "                    res[i] += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s: str) -> int:\n",
    "            cnt = Counter(s)\n",
    "            return cnt[min(cnt.keys())]\n",
    "        words_cnt = [f(s) for s in words]\n",
    "        words_cnt.sort()\n",
    "        queries_cnt = [f(q) for q in queries]\n",
    "        ans = []\n",
    "        n = len(words_cnt)\n",
    "        for q in queries_cnt:\n",
    "            left,right = 0,n-1\n",
    "            while left<=right:\n",
    "                mid = (left+right)//2\n",
    "                if q >= words_cnt[mid]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            ans.append(n-left)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        ret = []\n",
    "        m, n = len(queries), len(words)\n",
    "        my_list1 = [0]*m\n",
    "        my_list2 = [0]*n\n",
    "        def func(str):\n",
    "            cnt = 0\n",
    "            ch = 'z'\n",
    "            for c in str:\n",
    "                if c < ch:\n",
    "                    ch = c\n",
    "                    cnt = 1\n",
    "                elif c == ch:\n",
    "                    cnt+=1\n",
    "            return cnt\n",
    "            \n",
    "        for i in range(m):\n",
    "            my_list1[i] = func(queries[i])\n",
    "        for j in range(n):\n",
    "            my_list2[j] = func(words[j])\n",
    "        for i in range(m):\n",
    "            t = 0\n",
    "            for j in range(n):\n",
    "                if my_list1[i] < my_list2[j]:\n",
    "                    t+=1\n",
    "            ret +=[t]\n",
    "        return ret\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            ans = [0 for _ in range(26)]\n",
    "            for i in s:\n",
    "                ans[ord(i) - ord('a')] += 1\n",
    "            for i in range(26):\n",
    "                if ans[i] != 0:\n",
    "                    return ans[i]\n",
    "        n = len(words)\n",
    "        nums = sorted([f(w) for w in words])\n",
    "        return [n - bisect_right(nums, f(q)) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(x):\n",
    "            cnt = 0\n",
    "            cha = \"z\"\n",
    "            for subx in x:\n",
    "                if subx < cha:\n",
    "                    cha = subx\n",
    "                    cnt = 1\n",
    "                elif subx == cha:\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "        \n",
    "        cont = [0]*12\n",
    "        for word in words:\n",
    "            cont[f(word)] += 1\n",
    "        for i in range(9, 0, -1):\n",
    "            cont[i] += cont[i+1]\n",
    "        res = []\n",
    "        \n",
    "        for query in queries:\n",
    "            res.append(cont[f(query)+1])\n",
    "        return res \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s: str) -> int:\n",
    "            cnt = 0\n",
    "            ch = 'z'\n",
    "            for c in s:\n",
    "                if c < ch:\n",
    "                    ch = c\n",
    "                    cnt = 1\n",
    "                elif c == ch:\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "        count = [0] * 12\n",
    "        for s in map(f, words):\n",
    "            count[s] += 1\n",
    "        for i in range(9, 0, -1):\n",
    "            count[i] += count[i + 1]\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            res.append(count[f(s) + 1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSmaller(self, s):\n",
    "        # 排序并找到最小字符的频率\n",
    "        sorted_chars = sorted(s)\n",
    "        cnt = 1\n",
    "        for i in range(len(sorted_chars) - 1):\n",
    "            if sorted_chars[i] == sorted_chars[i + 1]:\n",
    "                cnt += 1\n",
    "            else:\n",
    "                break\n",
    "        return cnt\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        result_list = []\n",
    "        # 计算每个单词的最小字符频率\n",
    "        words_frequencies = [self.countSmaller(word) for word in words]\n",
    "        # 对于每个查询计算最小字符频率\n",
    "        for query in queries:\n",
    "            query_frequency = self.countSmaller(query)\n",
    "            # 计算有多少单词的最小字符频率大于查询的最小字符频率\n",
    "            count = sum(word_frequency > query_frequency for word_frequency in words_frequencies)\n",
    "            result_list.append(count)\n",
    "\n",
    "        return result_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        res = []\n",
    "        count = []\n",
    "        for word in words:\n",
    "            count.append(self.find_fre(word))\n",
    "        count.sort()\n",
    "        for query in queries:\n",
    "            query_freq = self.find_fre(query)\n",
    "            left, right = 0, len(words) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if query_freq >= count[mid]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            res.append(len(words) - left)\n",
    "        return res\n",
    "        \n",
    "\n",
    "    def find_fre(self, s : str) -> int:\n",
    "        min_char = min(s)\n",
    "        return s.count(min_char)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        a = sorted(s.count(min(s)) for s in words)\n",
    "        return [len(a) - bisect_right(a, q.count(min(q))) for q in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            cnt = Counter(s)\n",
    "            return next(cnt[c] for c in ascii_lowercase if cnt[c])\n",
    "        n = len(words)\n",
    "        nums = sorted(f(w) for w in words)\n",
    "        return [n -bisect_right(nums, f(q)) for q in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        all_count_list = []\n",
    "        all_word_list = queries + words\n",
    "        for query in all_word_list:\n",
    "            sorted_string = ''.join(sorted(query))\n",
    "            first_str = sorted_string[0]\n",
    "            min_str_count = 0\n",
    "            for str in sorted_string:\n",
    "                if str != first_str:\n",
    "                    break\n",
    "                min_str_count += 1\n",
    "            all_count_list.append(min_str_count)\n",
    "        query_list = all_count_list[0:len(queries)]\n",
    "        word_list = all_count_list[len(queries):]\n",
    "        single_query = set(query_list)\n",
    "        final_dict = {}\n",
    "        for count in single_query:\n",
    "            sum_count = sum(1 for number in word_list if number > count)\n",
    "            final_dict[count] = sum_count\n",
    "        return [final_dict[count] for count in query_list]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        ch = 'z'\n",
    "        for c in s:\n",
    "            if c < ch:\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "            elif c == ch:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        count = [0] * 12\n",
    "        for s in words:\n",
    "            count[self.f(s)] += 1\n",
    "        for i in range(9, 0, -1):\n",
    "            count[i] += count[i + 1]\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            res.append(count[self.f(s) + 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s):\n",
    "        return s.count(min(s))\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        a = sorted(self.f(s) for s in words)\n",
    "        return [len(a) - bisect_right(a, self.f(q)) for q in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            t = 'z'\n",
    "            for c in s:\n",
    "                if ord(t) > ord(c):\n",
    "                    t = c\n",
    "            return list(s).count(t)\n",
    "        q_x = list(map(f,queries))\n",
    "        w_x = list(map(f,words))\n",
    "        res = []\n",
    "        for i in q_x:\n",
    "            res.append(len(list(filter(lambda x:x>i,w_x))))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        \n",
    "        def f_counts(lst):\n",
    "            res = []\n",
    "            for query in lst:\n",
    "                query=list(query)\n",
    "                query.sort()\n",
    "                res.append(query.count(query[0]))\n",
    "\n",
    "            return res\n",
    "\n",
    "        ww = f_counts(words)\n",
    "        qq = f_counts(queries)\n",
    "\n",
    "        rr = []\n",
    "        for i in qq:\n",
    "            rr.append(sum(j > i for j in ww))\n",
    "\n",
    "        return rr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        \n",
    "        def f(s):\n",
    "            return sorted(Counter(s).items())[0][1]\n",
    "        \n",
    "        fq = [f(q) for q in queries]\n",
    "        fw = sorted([f(w) for w in words])\n",
    "        n = len(fw)\n",
    "\n",
    "        return [n - bisect_right(fw, q) for q in fq]\n",
    "        print(fq, fw)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        dic = [0] * len(words)\n",
    "        \n",
    "        def f(words):\n",
    "            return list(words).count(min(words))\n",
    "        \n",
    "        for i in range(len(words)):\n",
    "            dic[i] = f(words[i])\n",
    "        dic.sort()\n",
    "        # print(dic)\n",
    "\n",
    "        res = [0] * len(queries)\n",
    "        \n",
    "        for i in range(len(queries)):\n",
    "            cnt = f(queries[i])\n",
    "            # print(\"cnt\", cnt)\n",
    "            l = 0\n",
    "            r = len(dic) - 1\n",
    "            \n",
    "            res[i] = len(words) - bisect_right(dic, cnt)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        \n",
    "        def f(s):\n",
    "            return sorted(Counter(s).items())[0][1]\n",
    "        \n",
    "        fq = [f(q) for q in queries]\n",
    "        fw = sorted([f(w) for w in words])\n",
    "        n = len(fw)\n",
    "\n",
    "        return [n - bisect_right(fw, q) for q in map(f, queries)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s):\n",
    "        res = Counter(s)\n",
    "        return res[sorted(res.keys())[0]]\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = [self.f(s) for s in queries]\n",
    "        words = [self.f(s) for s in words]\n",
    "        words.sort()\n",
    "        n = len(words)\n",
    "        res = []\n",
    "        for i, q in enumerate(queries):\n",
    "           queries[i] = n - bisect_right(words, q)\n",
    "        return queries\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s):\n",
    "        res = Counter(s)\n",
    "        return res[sorted(res.keys())[0]]\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = [self.f(s) for s in queries]\n",
    "        words = [self.f(s) for s in words]\n",
    "        words.sort()\n",
    "        n = len(words)\n",
    "        for i, q in enumerate(queries):\n",
    "           queries[i] = n - bisect_right(words, q)\n",
    "        return queries\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        len_q = len(queries)\n",
    "        len_w = len(words)\n",
    "        ans = []\n",
    "        for x in queries:\n",
    "            count = 0\n",
    "            for y in words:\n",
    "                count_x = 0\n",
    "                count_y = 0\n",
    "                fir_x = x[0]\n",
    "                fir_y = y[0] \n",
    "                for i in x:\n",
    "                    if i == fir_x:\n",
    "                        count_x = count_x + 1\n",
    "                    if i < fir_x:\n",
    "                        count_x = 1\n",
    "                        fir_x = i\n",
    "                for i in y:\n",
    "                    if i == fir_y:\n",
    "                        count_y = count_y + 1\n",
    "                    if i < fir_y:\n",
    "                        count_y = 1\n",
    "                        fir_y = i\n",
    "                if count_x < count_y:\n",
    "                    count = count + 1\n",
    "            ans.append(count)\n",
    "        return ans\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            for i in range(97,123):\n",
    "                if chr(i) in s:\n",
    "                    break\n",
    "            return list(s).count(chr(i))\n",
    "        q_x = list(map(f,queries))\n",
    "        w_x = list(map(f,words))\n",
    "        res = []\n",
    "        for i in q_x:\n",
    "            res.append(len(list(filter(lambda x:x>i,w_x))))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            query_fre = self.find_fre(query)\n",
    "            count = 0\n",
    "            for word in words:\n",
    "                word_fre = self.find_fre(word)\n",
    "                if query_fre < word_fre:\n",
    "                    count += 1\n",
    "            res.append(count)\n",
    "        return res\n",
    "\n",
    "    def find_fre(self, s : str) -> int:\n",
    "        min_char = min(s)\n",
    "        return s.count(min_char)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        n = len(words)\n",
    "        nums = sorted(self.f(w) for w in words)\n",
    "        return [n - bisect_right(nums, self.f(q)) for q in queries]\n",
    "    \n",
    "    def f(self, s):\n",
    "        cnt = 0\n",
    "        ch = 'z'\n",
    "        for c in s:\n",
    "            if c < ch:\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "            elif c == ch:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            c = Counter(s)\n",
    "            return c[sorted(c)[0]]\n",
    "        c = Counter(map(f, words))\n",
    "        l = [[k,v] for k, v, in c.items()]\n",
    "        l.sort()\n",
    "        for i in range(len(l)-1):\n",
    "            l[-2-i][1] += l[-1-i][1]\n",
    "\n",
    "        a = [0] * len(queries)\n",
    "        for i, q in enumerate(queries):\n",
    "            j = bisect_right(l, [f(q), float('inf')])\n",
    "            if j < len(l):\n",
    "                a[i] = l[j][1]\n",
    "\n",
    "        return a\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s):\n",
    "        res = Counter(s)\n",
    "        return res[sorted(res.keys())[0]]\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = [self.f(s) for s in queries]\n",
    "        words = [self.f(s) for s in words]\n",
    "        words.sort()\n",
    "        n = len(words)\n",
    "        for i, q in enumerate(queries):\n",
    "           queries[i] = n - bisect_right(words, q)\n",
    "        return queries\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def alphaS(self,strs):\n",
    "        asc_num = [ord(s) for s in strs]\n",
    "        min_alpha = chr(min(asc_num))\n",
    "        cnt=0\n",
    "        for a in strs:\n",
    "            if a==min_alpha:\n",
    "                cnt+=1\n",
    "        return cnt \n",
    "\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        \n",
    "        fws =[ self.alphaS(word) for word in words]\n",
    "        rnt = []\n",
    "        for i in queries:\n",
    "            cnt = 0\n",
    "            fi = self.alphaS(i)\n",
    "            for fw in fws:  \n",
    "                if fi<fw:\n",
    "                    cnt+=1\n",
    "            rnt.append(cnt)\n",
    "        return rnt\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s: str) -> int:\n",
    "            cnt = Counter(s)\n",
    "            return cnt[min(cnt.keys())]\n",
    "        words_cnt = [f(s) for s in words]\n",
    "        words_cnt.sort()\n",
    "        queries_cnt = [f(q) for q in queries]\n",
    "        ans = []\n",
    "        n = len(words_cnt)\n",
    "        for q in queries_cnt:\n",
    "            left,right = 0,n-1\n",
    "            while left<=right:\n",
    "                mid = (left+right)//2\n",
    "                if q >= words_cnt[mid]:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            ans.append(n-left)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            cnt = Counter(s)\n",
    "            minKey = min(cnt.keys())\n",
    "            return cnt[minKey]\n",
    "        W = [f(s) for s in words]\n",
    "        W.sort()\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            fs = f(q)\n",
    "            index = bisect_right(W, fs)\n",
    "            res.append(len(W) - index)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(x):\n",
    "            l = len(x)\n",
    "            s = {}\n",
    "            for i in range(l):\n",
    "                if x[i] in s.keys():\n",
    "                    s[x[i]] += 1\n",
    "                else:\n",
    "                    s[x[i]] = 1\n",
    "            return s[sorted(s)[0]]\n",
    "        quer = [f(x) for x in queries]\n",
    "        w = sorted([f(x) for x in words])\n",
    "        res = []\n",
    "        wo = [0,0,0,0,0,0,0,0,0,0]\n",
    "        for i in range(len(w)):\n",
    "            wo[w[i]-1] += 1\n",
    "        for i in range(len(quer)):\n",
    "            res.append(sum(wo[quer[i]::]))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = self.StrToInt(queries)\n",
    "        words = self.StrToInt(words)\n",
    "\n",
    "        answer = []\n",
    "\n",
    "        for query in queries:\n",
    "            sub_answer = 0\n",
    "            for word in words:\n",
    "                if query < word:\n",
    "                    sub_answer += 1\n",
    "\n",
    "            answer.append(sub_answer)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "    def StrToInt(self, data: List[str]) -> List[int]:\n",
    "        new_list = []\n",
    "\n",
    "        for i in data:\n",
    "            min_ord = 1000\n",
    "            min_count = 0\n",
    "\n",
    "            for ii in i:\n",
    "                if ord(ii) < min_ord:\n",
    "                    min_ord = ord(ii)\n",
    "                    min_count = 1\n",
    "                if ord(ii) == min_ord:\n",
    "                    min_count += 1\n",
    "\n",
    "            new_list.append(min_count)\n",
    "        \n",
    "        return new_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            nums=[0]*26\n",
    "            l=26\n",
    "            for i in range(len(s)):\n",
    "                nums[ord(s[i])-ord('a')]+=1\n",
    "                l=min(l,ord(s[i])-ord('a'))\n",
    "            return nums[l]\n",
    "        words_f=[]\n",
    "        for word in words:\n",
    "            words_f.append(f(word))\n",
    "        words_f.sort()\n",
    "        ans=[]\n",
    "        for query in queries:\n",
    "            q=f(query)\n",
    "            r=bisect.bisect_right(words_f, q)\n",
    "            ans.append(len(words)-r)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            # the input s is a list\n",
    "            cnt = Counter(s)\n",
    "            return cnt[min(cnt)]\n",
    "        ans = []\n",
    "        word_list = [f(s) for s in words]\n",
    "        for q in queries:\n",
    "            num = f(q)\n",
    "            cnt = 0\n",
    "            for w in word_list:\n",
    "                if num < w:\n",
    "                    cnt += 1\n",
    "            ans.append(cnt)\n",
    "        return ans\n",
    "\n",
    "        # for i,q in enumerate(queries):\n",
    "        #     cnt = 0\n",
    "        #     for j in words:\n",
    "        #         if f(q) < f(j):\n",
    "        #             cnt += 1\n",
    "        #     ans[i] = cnt\n",
    "        # return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def F(s):\n",
    "    smallest_c = s[0]\n",
    "    count = 0\n",
    "    for c in s:\n",
    "        if smallest_c < c:\n",
    "            continue\n",
    "        elif smallest_c > c:\n",
    "            smallest_c = c\n",
    "            count = 1\n",
    "        else:\n",
    "            count+=1\n",
    "    return count\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        f_words = list(map(lambda x: F(x), words))\n",
    "\n",
    "        result = []\n",
    "        for query in queries:\n",
    "            f_query = F(query)\n",
    "            count = sum(f_word > f_query for f_word in f_words)\n",
    "            result.append(count)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s):\n",
    "        res = Counter(s)\n",
    "        return res[sorted(res.keys())[0]]\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = [self.f(s) for s in queries]\n",
    "        words = [self.f(s) for s in words]\n",
    "        words.sort()\n",
    "        n = len(words)\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            res.append(n - bisect_right(words, q))\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = self.StrToInt(queries)\n",
    "        words = self.StrToInt(words)\n",
    "        print(queries, words)\n",
    "\n",
    "        answer = []\n",
    "\n",
    "        for index, query in enumerate(queries):\n",
    "            sub_answer = 0\n",
    "            for word in words:\n",
    "                if query < word:\n",
    "                    sub_answer += 1\n",
    "\n",
    "            answer.append(sub_answer)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "    def StrToInt(self, data: List[str]) -> List[int]:\n",
    "        new_list = []\n",
    "\n",
    "        for i in data:\n",
    "            i_dict = {}\n",
    "            min_ord = 1000\n",
    "            min_count = 0\n",
    "\n",
    "            for ii in i:\n",
    "                i_dict[ii] = i_dict.get(ii, 0) + 1\n",
    "\n",
    "            for k, v in i_dict.items():\n",
    "                if ord(k) < min_ord:\n",
    "                    min_ord = ord(k)\n",
    "                    min_count = v\n",
    "            \n",
    "            new_list.append(min_count)\n",
    "        \n",
    "        return new_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def fun(chars: str):\n",
    "            num = 1\n",
    "            char = chars[0]\n",
    "            for c in chars[1:]:\n",
    "                if c < char:\n",
    "                    char = c\n",
    "                    num = 1\n",
    "                elif c == char:\n",
    "                    num += 1\n",
    "            return num\n",
    "\n",
    "        word_nums = [fun(word) for word in words]\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            num = fun(q)\n",
    "            s = 0\n",
    "            for word_num in word_nums:\n",
    "                if word_num > num:\n",
    "                    s += 1\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(x):\n",
    "            l = len(x)\n",
    "            s = {}\n",
    "            for i in range(l):\n",
    "                if x[i] in s.keys():\n",
    "                    s[x[i]] += 1\n",
    "                else:\n",
    "                    s[x[i]] = 1\n",
    "            return s[sorted(s)[0]]\n",
    "        quer = [f(x) for x in queries]\n",
    "        w = sorted([f(x) for x in words])\n",
    "        # print(quer)\n",
    "        # print(w)\n",
    "        res = []\n",
    "        for i in range(len(quer)):\n",
    "            r = 0\n",
    "            for j in range(len(w)):\n",
    "                if w[-(j+1)]>quer[i]:\n",
    "                    r += 1\n",
    "            res.append(r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(string):\n",
    "            ans = 0\n",
    "            last_char = ''\n",
    "            for x in sorted(string):\n",
    "                if last_char and last_char != x:\n",
    "                    break\n",
    "                ans +=1\n",
    "                last_char = x\n",
    "            return ans\n",
    "        \n",
    "        nums = []\n",
    "        for w in words:\n",
    "            nums.append(f(w))\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        for q in queries:\n",
    "            cnt = f(q)\n",
    "            val = bisect.bisect(nums, cnt)\n",
    "            res.append(len(nums)-val)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        \n",
    "        def test(strs):\n",
    "            cnt = 0\n",
    "            ch = 'z'\n",
    "            for c in strs:\n",
    "                if c < ch:\n",
    "                    ch = c\n",
    "                    cnt = 1\n",
    "                elif c == ch:\n",
    "                    cnt += 1\n",
    "            return cnt\n",
    "\n",
    "        t1,t2 = [test(i) for i in queries],[test(i) for i in words]\n",
    "        t =[]\n",
    "\n",
    "        for i in t1 :\n",
    "            n=0\n",
    "            for j in t2 :\n",
    "                if i<j:\n",
    "                    n+= 1\n",
    "            t.append(n)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s):\n",
    "        res = Counter(s)\n",
    "        return res[sorted(res.keys())[0]]\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = [self.f(s) for s in queries]\n",
    "        words = [self.f(s) for s in words]\n",
    "        words.sort()\n",
    "        n = len(words)\n",
    "        for i, q in enumerate(queries):\n",
    "           queries[i] = n - bisect_right(words, q)\n",
    "        return queries\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def f(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        ch = 'z'\n",
    "        for c in s:\n",
    "            if c < ch:\n",
    "                ch = c\n",
    "                cnt = 1\n",
    "            elif c == ch:\n",
    "                cnt += 1\n",
    "        return cnt\n",
    "\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        count = [0] * 12\n",
    "        for s in words:\n",
    "            count[self.f(s)] += 1\n",
    "        for i in range(9, 0, -1):\n",
    "            count[i] += count[i + 1]\n",
    "        res = []\n",
    "        for s in queries:\n",
    "            res.append(count[self.f(s) + 1])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def getnums(s):\n",
    "            mini = s[0]\n",
    "            mini_nums = 1\n",
    "            for i in range(1,len(s)):\n",
    "                if s[i] < mini:\n",
    "                    mini = s[i]\n",
    "                    mini_nums = 1\n",
    "                elif s[i] == mini:\n",
    "                    mini_nums += 1\n",
    "                else:\n",
    "                    continue\n",
    "            return mini_nums\n",
    "        \n",
    "        que,wor,res = [],[],[]\n",
    "        for i in queries:\n",
    "            que.append(getnums(i))\n",
    "        for i in words:\n",
    "            wor.append(getnums(i))\n",
    "        \n",
    "        wor.sort()\n",
    "        for i in que:\n",
    "            a = bisect.bisect(wor,i+0.5)\n",
    "            a = len(wor) - a\n",
    "            res.append(a)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f( s ):\n",
    "            word_dic = collections.defaultdict(int)\n",
    "            for i in s:\n",
    "                word_dic[i] += 1\n",
    "            return sorted( word_dic.items() , key = lambda x:x[0])[0][1]\n",
    "\n",
    "        queries_val = [f(i) for i in queries]\n",
    "        words_val = [f(i) for i in words ]\n",
    "        words_val.sort( reverse=True)\n",
    "        res = []\n",
    "        for qval in queries_val:\n",
    "            tmp_cnt = 0\n",
    "            for wval in words_val:\n",
    "                if qval < wval:\n",
    "                    tmp_cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "            res.append(tmp_cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def calc_f(s: str):\n",
    "            ans = 0\n",
    "            cur = 'z'\n",
    "            for c in s:\n",
    "                if c < cur:\n",
    "                    cur = c\n",
    "                    ans = 1\n",
    "                elif c == cur:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    continue\n",
    "            return ans\n",
    "\n",
    "        words_f = [calc_f(x) for x in words]\n",
    "        words_f.sort()\n",
    "        res = []\n",
    "        n = len(words_f)\n",
    "        for q in queries:\n",
    "            q_f = calc_f(q)\n",
    "            ind = bisect.bisect_right(words_f, q_f)\n",
    "            res.append(n-ind)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        queries = self.StrToInt(queries)\n",
    "        words = self.StrToInt(words)\n",
    "\n",
    "        answer = []\n",
    "\n",
    "        for index, query in enumerate(queries):\n",
    "            sub_answer = 0\n",
    "            for word in words:\n",
    "                if query < word:\n",
    "                    sub_answer += 1\n",
    "\n",
    "            answer.append(sub_answer)\n",
    "\n",
    "        return answer\n",
    "\n",
    "\n",
    "    def StrToInt(self, data: List[str]) -> List[int]:\n",
    "        new_list = []\n",
    "\n",
    "        for i in data:\n",
    "            i_dict = {}\n",
    "            min_ord = 1000\n",
    "            min_count = 0\n",
    "\n",
    "            for ii in i:\n",
    "                i_dict[ii] = i_dict.get(ii, 0) + 1\n",
    "\n",
    "            for k, v in i_dict.items():\n",
    "                if ord(k) < min_ord:\n",
    "                    min_ord = ord(k)\n",
    "                    min_count = v\n",
    "            \n",
    "            new_list.append(min_count)\n",
    "        \n",
    "        return new_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        w = [word.count(min(word)) for word in words]\n",
    "        w.sort(reverse=True)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            f = q.count(min(q))\n",
    "            count = 0\n",
    "            for amount in w:\n",
    "                if f >= amount:\n",
    "                    break\n",
    "                count += 1\n",
    "            ans.append(count)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def f(s):\n",
    "            return s.count(min(s))\n",
    "        lst_f_words = [f(item) for item in words]\n",
    "        lst_f_words.sort(reverse = True)\n",
    "        def cont(n):\n",
    "            i = 0\n",
    "            while i<len(lst_f_words) and int(n) < lst_f_words[i]:\n",
    "                i+=1\n",
    "            return i\n",
    "        return [cont(f(item)) for item in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        query=[]\n",
    "        for w in words:\n",
    "            c=min(w)\n",
    "            query.append(w.count(c))\n",
    "        query.sort()\n",
    "        arr=[]\n",
    "        for i in range(len(queries)):\n",
    "            c=min(queries[i])\n",
    "            arr.append([i,queries[i].count(c)])\n",
    "        arr.sort(key=lambda x:x[1])\n",
    "        res=[0]*len(arr)\n",
    "        x=0\n",
    "        while arr:\n",
    "            i,a=arr.pop()\n",
    "            while query and query[-1]>a:\n",
    "                x+=1\n",
    "                query.pop()\n",
    "            res[i]=x\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        ans=[0]*len(queries)\n",
    "        W=[]\n",
    "        for s in words:\n",
    "            W.append(s.count(min(s)))\n",
    "        for i in range(len(queries)):\n",
    "            q=queries[i]\n",
    "            val=q.count(min(q))\n",
    "            count=0\n",
    "            for w in W:\n",
    "                if w>val:\n",
    "                    count+=1\n",
    "            ans[i]=count\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        all_count_list = []\n",
    "        all_word_list = queries + words\n",
    "        for query in all_word_list:\n",
    "            sorted_string = ''.join(sorted(query))\n",
    "            first_str = sorted_string[0]\n",
    "            min_str_count = 0\n",
    "            for str in sorted_string:\n",
    "                if str != first_str:\n",
    "                    break\n",
    "                min_str_count += 1\n",
    "            all_count_list.append(min_str_count)\n",
    "        query_list = all_count_list[0:len(queries)]\n",
    "        word_list = all_count_list[len(queries):]\n",
    "        final_list = []\n",
    "        for count in query_list:\n",
    "            final_list.append(self.count_greater_than(word_list, count))\n",
    "        return final_list\n",
    "\n",
    "    def count_greater_than(self, numbers, threshold):\n",
    "        count = sum(1 for number in numbers if number > threshold)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        def getnums(s):\n",
    "            mini = s[0]\n",
    "            mini_nums = 1\n",
    "            for i in range(1,len(s)):\n",
    "                if s[i] < mini:\n",
    "                    mini = s[i]\n",
    "                    mini_nums = 1\n",
    "                elif s[i] == mini:\n",
    "                    mini_nums += 1\n",
    "                else:\n",
    "                    continue\n",
    "            return mini_nums\n",
    "        \n",
    "        que,wor,res = [],[],[]\n",
    "        for i in queries:\n",
    "            que.append(getnums(i))\n",
    "        for i in words:\n",
    "            wor.append(getnums(i))\n",
    "        \n",
    "        for i in que:\n",
    "            count = 0\n",
    "            for j in wor:\n",
    "                if j > i:\n",
    "                    count += 1\n",
    "            res.append(count)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:\n",
    "        nw = []\n",
    "\n",
    "        for word in words:\n",
    "            sw = list(word)\n",
    "            sw.sort()\n",
    "            cnt = 1\n",
    "            for i in range(1, len(sw)):\n",
    "                if sw[i] == sw[i-1]:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            nw.append(cnt)\n",
    "        nw.sort()\n",
    "        # print(nw)\n",
    "        ans = []\n",
    "        for q in queries:\n",
    "            sq = list(q)\n",
    "            sq.sort()\n",
    "            qcnt = 1\n",
    "            for i in range(1, len(sq)):\n",
    "                if sq[i] == sq[i-1]:\n",
    "                    qcnt += 1\n",
    "                else:\n",
    "                    break\n",
    "            pos = bisect.bisect_right(nw, qcnt)\n",
    "            ans.append(len(words) - pos)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
